package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
 *
 * @Author: haogege
 * @Date: 2021/9/13
 */
public class _188_买卖股票的最佳时机IV {

    public static void main(String[] args) {

        _188_买卖股票的最佳时机IV iv = new _188_买卖股票的最佳时机IV();
        int[] ins = {3, 3, 5, 0, 0, 3, 1, 4};
        int i = iv.maxProfit(2, ins);

        System.out.println(i);

    }


    public int maxProfit(int k, int[] prices) {
        if (k == 0 || prices.length < 2) return 0;
        // 当大于一半时，可以使用贪心算法
        if (k >= prices.length >> 1) return greedy(prices);
        // 找出k比数据的间隙最大的
        int[][] dp = new int[k][2];
        // 初始化数据
        for (int i = 0; i < k; i++) {
            dp[i][0] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            dp[0][0] = Math.max(dp[0][0], -prices[i]);
            dp[0][1] = Math.max(dp[0][1], dp[0][0] + prices[i]);
            for (int j = 1; j < k; j++) {
                dp[j][0] = Math.max(dp[j][0],  dp[j - 1][1] - prices[i]);
                dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);
            }
        }
        return dp[k - 1][1];
    }

    private int greedy(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(0, prices[i] - prices[i - 1]);
        }
        return result;
    }

    public int maxProfit1(int k, int[] prices) {
        if (k == 0 || prices.length < 2) return 0;

        // 定义二维dp数组
        int[][] dp = new int[k][2];
        // 初始化数据
        for (int i = 0; i < k; i++) {
            dp[i][0] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            // 遍历dp数组
            for (int j = 0; j < dp.length; j++) {
                dp[j][0] = Math.max(dp[j][0], (j - 1 < 0 ? 0 : dp[j - 1][1]) - prices[i]);
                dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);
            }
        }
        return dp[k - 1][1];
    }

}
